package Exercise;

import java.util.Scanner;
public class Binary_sort {
    public static void main(String[] args){
        //arr【0】不放元素
        int[] arr= new int[11];
        Scanner sc = new Scanner(System.in);
        System.out.println("输入10个数字：");
        for(int i = 1;i<arr.length;i++){
            int num = sc.nextInt();
            arr[i] = num;
        }
        System.out.print("排序前：");
        Put(arr);
        System.out.print("排序后：");
        Binarysort(arr);
        Put(arr);
    }
    //输出
    public static void Put(int[] arr){
        for(int i = 1;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
    //折半插入排序
    public static void Binarysort(int[] arr) {
        //先通过折半查找法，找到插入的位置
        for (int i = 2; i <= arr.length-1; i++) {
            arr[0] = arr[i];
            //第i个待排序的数前面有序，从第一个到第i-1个数中进行查找
            int low = 1;
            int high = i - 1;
            //通过循环不断逼近放入的位置，循环结束后low或者high+1就是放入的位置
            while (low <= high) {
                int mid = (int) ((low + high) / 2);
                if (arr[0] <= arr[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            //将下标从low或者high+1，到i-1的数，依次向后面移动一位
            for(int j = i-1;j>high;--j)
                arr[j+1] = arr[j];
            arr[high+1] = arr[0];
        }
    }
}


